package com.yanceysong.codetop.s1_s10;

import java.util.HashMap;

/**
 * @ClassName S2_Mid_3_无重复最长子串
 * @Description
 * @date 2024/6/4 下午1:19
 * @Author yanceysong
 * @Version 1.0
 */
public class S1_Mid_3_无重复最长子串 {
    /**
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度
     * 示例 1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        //用于记录最大不重复子串的长度
        int maxLen = 0;
        //滑动窗口左指针
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            /*
             1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

             2、如果当前字符 ch 包含在 map中，此时有2类情况：
                1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
                2）当前字符不包含在当前最长有效子段中，如：abba。
                我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
             随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
             应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if (map.containsKey(s.charAt(i))) {
                // 这里为了解决abba的情况，第一次窗口移动到了b，
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        S1_Mid_3_无重复最长子串 solution = new S1_Mid_3_无重复最长子串();

        System.out.println("=== 无重复最长子串测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 特殊字符测试
        System.out.println("\n--- 测试3: 特殊字符测试 ---");
        testSpecialCharacters(solution);

        // 测试4: 复杂重复模式测试
        System.out.println("\n--- 测试4: 复杂重复模式测试 ---");
        testComplexPatterns(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S1_Mid_3_无重复最长子串 solution) {
        // 示例1: "abcabcbb" -> 3 ("abc")
        String s1 = "abcabcbb";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 3, 子串: \"abc\")");
        assert result1 == 3 : "abcabcbb的最长无重复子串长度应该是3";

        // 示例2: "bbbbb" -> 1 ("b")
        String s2 = "bbbbb";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 1, 子串: \"b\")");
        assert result2 == 1 : "bbbbb的最长无重复子串长度应该是1";

        // 示例3: "pwwkew" -> 3 ("wke")
        String s3 = "pwwkew";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 3, 子串: \"wke\")");
        assert result3 == 3 : "pwwkew的最长无重复子串长度应该是3";

        // 示例4: "abba" -> 2 ("ab" 或 "ba")
        String s4 = "abba";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 2, 子串: \"ab\" 或 \"ba\")");
        assert result4 == 2 : "abba的最长无重复子串长度应该是2";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCase(S1_Mid_3_无重复最长子串 solution) {
        // 空字符串
        String s1 = "";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 0)");
        assert result1 == 0 : "空字符串的最长无重复子串长度应该是0";

        // 单个字符
        String s2 = "a";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 1)");
        assert result2 == 1 : "单个字符的最长无重复子串长度应该是1";

        // 两个相同字符
        String s3 = "aa";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 1)");
        assert result3 == 1 : "两个相同字符的最长无重复子串长度应该是1";

        // 两个不同字符
        String s4 = "ab";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 2)");
        assert result4 == 2 : "两个不同字符的最长无重复子串长度应该是2";

        // 全部字符都不重复
        String s5 = "abcdefg";
        int result5 = solution.lengthOfLongestSubstring(s5);
        System.out.println("输入: \"" + s5 + "\" -> 输出: " + result5 + " (期望: 7)");
        assert result5 == 7 : "全部不重复字符的最长无重复子串长度应该等于字符串长度";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 修正方法名并实现边界情况测试
     */
    private static void testBoundaryCases(S1_Mid_3_无重复最长子串 solution) {
        testBoundaryCase(solution);
    }

    /**
     * 测试特殊字符
     */
    private static void testSpecialCharacters(S1_Mid_3_无重复最长子串 solution) {
        // 包含空格
        String s1 = "a b c a";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 3, 子串: \"a b\" 或 \"b c\")");
        assert result1 == 3 : "包含空格的字符串测试失败";

        // 包含数字
        String s2 = "123321";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 3, 子串: \"123\" 或 \"321\")");
        assert result2 == 3 : "包含数字的字符串测试失败";

        // 包含特殊符号
        String s3 = "!@#$%!";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 5, 子串: \"!@#$%\")");
        assert result3 == 5 : "包含特殊符号的字符串测试失败";

        // 混合字符
        String s4 = "a1!b2@a";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 6, 子串: \"1!b2@a\")");
        assert result4 == 6 : "混合字符的字符串测试失败";

        System.out.println("✓ 特殊字符测试通过");
    }

    /**
     * 测试复杂重复模式
     */
    private static void testComplexPatterns(S1_Mid_3_无重复最长子串 solution) {
        // 测试abba模式（代码注释中的特殊情况）
        String s1 = "abba";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 2, 验证abba特殊情况)");
        assert result1 == 2 : "abba模式测试失败";

        // 测试更复杂的abba模式
        String s2 = "abcba";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 3, 子串: \"abc\" 或 \"cba\")");
        assert result2 == 3 : "abcba模式测试失败";

        // 测试回文模式
        String s3 = "abccba";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 3, 子串: \"abc\" 或 \"cba\")");
        assert result3 == 3 : "回文模式测试失败";

        // 测试长距离重复
        String s4 = "abcdefga";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 7, 子串: \"bcdefga\")");
        assert result4 == 7 : "长距离重复测试失败";

        // 测试多个重复点
        String s5 = "abcabcabcabc";
        int result5 = solution.lengthOfLongestSubstring(s5);
        System.out.println("输入: \"" + s5 + "\" -> 输出: " + result5 + " (期望: 3, 子串: \"abc\")");
        assert result5 == 3 : "多个重复点测试失败";

        // 测试交替模式
        String s6 = "ababab";
        int result6 = solution.lengthOfLongestSubstring(s6);
        System.out.println("输入: \"" + s6 + "\" -> 输出: " + result6 + " (期望: 2, 子串: \"ab\")");
        assert result6 == 2 : "交替模式测试失败";

        System.out.println("✓ 复杂重复模式测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S1_Mid_3_无重复最长子串 solution) {
        // 构造较长的字符串进行性能测试
        StringBuilder sb = new StringBuilder();

        // 测试1: 长字符串，无重复
        for (int i = 0; i < 1000; i++) {
            sb.append((char) ('a' + (i % 26)));
        }
        String longString1 = sb.toString();

        long startTime = System.currentTimeMillis();
        int result1 = solution.lengthOfLongestSubstring(longString1);
        long endTime = System.currentTimeMillis();

        System.out.println("长字符串测试1 (1000字符，循环字母): " + result1 + " (期望: 26)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result1 == 26 : "长字符串性能测试1失败";

        // 测试2: 长字符串，全部相同
        String longString2 = "a".repeat(1000);

        startTime = System.currentTimeMillis();
        int result2 = solution.lengthOfLongestSubstring(longString2);
        endTime = System.currentTimeMillis();

        System.out.println("长字符串测试2 (1000个相同字符): " + result2 + " (期望: 1)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result2 == 1 : "长字符串性能测试2失败";

        // 测试3: 长字符串，最坏情况（每两个字符重复）
        sb = new StringBuilder();
        sb.append("ab".repeat(500));
        String longString3 = sb.toString();

        startTime = System.currentTimeMillis();
        int result3 = solution.lengthOfLongestSubstring(longString3);
        endTime = System.currentTimeMillis();

        System.out.println("长字符串测试3 (1000字符，ab重复): " + result3 + " (期望: 2)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result3 == 2 : "长字符串性能测试3失败";

        System.out.println("✓ 性能测试通过");
    }


}
